# LeetCode 42、接雨水
# 一、题目描述
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
# 二、题目解析
我们按照行方向去接雨水。
接下来我们去寻找凹槽。
一个凹槽是由三个柱子围成的。（这里为了描述方便，我们把高度为 0 的柱子也当成存在的柱子）
对于这个凹槽来说，它的左侧和底部是由栈中挑选出来的，右侧是由新添加的柱子决定的。
什么情况会出现凹槽呢？
一旦新添加的柱子高度大于栈顶元素，就有可能形成凹槽！
这个时候，栈顶元素是凹槽的底部，如果在栈中存在栈顶元素之前的元素，那么栈顶元素之前的元素就是凹槽的左侧，此时添加的元素是凹槽的右侧。
这里之所以是说有可能，是因为柱子里面可能是两根高度一样的柱子，即使新添加的柱子高度都大于它们，也是无法构成凹槽，或者说构成了一个面积为 0 的凹槽。
如果新添加的柱子高度小于栈顶元素，那么必然无法和当前的栈中元素构成一个凹槽，**因为这是一个单调栈，里面的元素越靠近栈顶越小，新添加的柱子高度都小于了栈顶元素，那必然小于里面其它的元素，**这种情况下，无法围成一个凹槽，我们就把当前的柱子加入到我们的栈中，让它和里面的柱子一起等待接下来的柱子。
如果新添加的柱子高度等于栈顶元素，也是无法形成凹槽的，我们就把当前的柱子加入到我们的栈中，让它和里面的柱子一起等待接下来的柱子。
一旦形成了凹槽，我们去计算它的面积。
面积由高和宽决定。
凹槽的高度是由 min(凹槽左边高度, 凹槽右边高度) - 凹槽底部高度 来计算的。
凹槽的宽度是由**凹槽右边的下标 - 凹槽左边的下标 - 1（因为只求中间宽度）**来计算的。
计算完一个凹槽的面积之后，我们就把栈顶元素弹出，观察剩下的那些栈中的元素能否和新添加的元素再构成一个新的凹槽。
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 接雨水（ LeetCode 42 ）:https://leetcode-cn.com/problems/trapping-rain-water/
class Solution {
public int trap(int[] height) {
// 只有两根柱子，必然无法形成一个凹槽，那么水的面积就是 0
if (height.length <= 2) return 0;
// 构建一个栈，用来存储对应的柱子的下标
// 注意：stack 存储的是下标而非高度
Stack<Integer> stack = new Stack<>();
// 一开始水的面积是 0
int result = 0;
// 从头开始遍历整个数组
for (int i = 0; i < height.length; i++) {
// 如果栈为空，那么直接把当前索引加入到栈中
if(stack.isEmpty()){
// 把当前索引加入到栈中
stack.push(i);
// 否则的话，栈里面是有值的，我们需要去判断此时的元素、栈顶元素、栈顶之前的元素能否形成一个凹槽
// 情况一：此时的元素小于栈顶元素，凹槽的右侧不存在，无法形成凹槽
}else if (height[i] < height[stack.peek()]) {
// 把当前索引加入到栈中
stack.push(i);
// 情况二：此时的元素等于栈顶元素，也是无法形成凹槽
} if (height[i] == height[stack.peek()]) {
// 把当前索引加入到栈中
stack.push(i);
// 情况三：此时的的元素大于栈顶元素，有可能形成凹槽
// 注意是有可能形成，因为比如栈中的元素是 2 、2 ，此时的元素是 3，那么是无法形成凹槽的
} else {
// 由于栈中有可能存在多个元素，移除栈顶元素之后，剩下的元素和此时的元素也有可能形成凹槽
// 因此，我们需要不断的比较此时的元素和栈顶元素
// 此时的元素依旧大于栈顶元素时，我们去计算此时的凹槽面积
// 借助 while 循环来实现这个操作
while (!stack.empty() && height[i] > height[stack.peek()]) {
// 1、获取栈顶的下标，bottom 为凹槽的底部位置
int bottom = stack.peek();
// 将栈顶元素推出，去判断栈顶之前的元素是否存在，即凹槽的左侧是否存在
stack.pop();
// 2、如果栈不为空，即栈中有元素，即凹槽的左侧存在
if (!stack.empty()) {
// 凹槽左侧的高度 height[stack.peek() 和 凹槽右侧的高度 height[i]
// 这两者的最小值减去凹槽底部的高度就是凹槽的高度
int h = Math.min(height[stack.peek()], height[i]) - height[bottom];
// 凹槽的宽度等于凹槽右侧的下标值 i 减去凹槽左侧的下标值 stack.peek 再减去 1
int w = i - stack.peek() - 1;
System.out.println("凹槽右侧-->" + i);
System.out.println("凹槽左侧-->" + stack.peek());
System.out.println("凹槽高度-->" + h);
System.out.println("凹槽宽度-->" + w);
System.out.println("凹槽面积-->" + h * w);
System.out.println("---------------");
// 将计算的结果累加到最终的结果上去
result += h * w;
}
}
// 栈中和此时的元素可以形成栈的情况在上述 while 循环中都已经判断了
// 那么，此时栈中的元素必然不可能大于此时的元素，所以可以把此时的元素添加到栈中
stack.push(i);
}
}
// 最后返回结果即可
return result;
}
}
# **2、**C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 接雨水（ LeetCode 42 ）:https://leetcode-cn.com/problems/trapping-rain-water/
class Solution {
public:
int trap(vector<int>& height) {
// 只有两根柱子，必然无法形成一个凹槽，那么水的面积就是 0
if (height.size() <= 2) return 0;
// 构建一个栈，用来存储对应的柱子的下标
// 注意：stk 存储的是下标而非高度
stack<int> stk ;
// 一开始水的面积是 0
int result = 0;
// 从头开始遍历整个数组
for (int i = 0; i < height.size(); i++) {
// 如果栈为空，那么直接把当前索引加入到栈中
if(stk.empty()){
// 把当前索引加入到栈中
stk.push(i);
// 否则的话，栈里面是有值的，我们需要去判断此时的元素、栈顶元素、栈顶之前的元素能否形成一个凹槽
// 情况一：此时的元素小于栈顶元素，凹槽的右侧不存在，无法形成凹槽
}else if (height[i] < height[stk.top()]) {
// 把当前索引加入到栈中
stk.push(i);
// 情况二：此时的元素等于栈顶元素，也是无法形成凹槽
} else if (height[i] == height[stk.top()]) {
// 把当前索引加入到栈中
stk.push(i);
// 情况三：此时的的元素大于栈顶元素，有可能形成凹槽
// 注意是有可能形成，因为比如栈中的元素是 2 、2 ，此时的元素是 3，那么是无法形成凹槽的
} else {
// 由于栈中有可能存在多个元素，移除栈顶元素之后，剩下的元素和此时的元素也有可能形成凹槽
// 因此，我们需要不断的比较此时的元素和栈顶元素
// 此时的元素依旧大于栈顶元素时，我们去计算此时的凹槽面积
// 借助 while 循环来实现这个操作
while (!stk.empty() && height[i] > height[stk.top()]) {
// 1、获取栈顶的下标，bottom 为凹槽的底部位置
int bottom = stk.top();
// 将栈顶元素推出，去判断栈顶之前的元素是否存在，即凹槽的左侧是否存在
stk.pop();
// 2、如果栈不为空，即栈中有元素，即凹槽的左侧存在
if (!stk.empty()) {
// 凹槽左侧的高度 height[stk.top() 和 凹槽右侧的高度 height[i]
// 这两者的最小值减去凹槽底部的高度就是凹槽的高度
int h = min(height[stk.top()], height[i]) - height[bottom];
// 凹槽的宽度等于凹槽右侧的下标值 i 减去凹槽左侧的下标值 stk.top 再减去 1
int w = i - stk.top() - 1;
// 将计算的结果累加到最终的结果上去
result += h * w;
}
}
// 栈中和此时的元素可以形成栈的情况在上述 while 循环中都已经判断了
// 那么，此时栈中的元素必然不可能大于此时的元素，所以可以把此时的元素添加到栈中
stk.push(i);
}
}
// 最后返回结果即可
return result;
}
};
# 3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 接雨水（ LeetCode 42 ）:https://leetcode-cn.com/problems/trapping-rain-water/
class Solution:
def trap(self, height: List[int]) -> int:
# 构建一个栈，用来存储对应的柱子的下标
# stack 存储的是下标而非高度
stack = list()
# 一开始水的面积是 0
result = 0
# 获取数组的长度
n = len(height)
# 从头开始遍历整个数组
for i, h in enumerate(height):
# 如果栈为空，那么直接把当前索引加入到栈中
if not stack :
# 把当前索引加入到栈中
stack.append(i)
# 否则的话，栈里面是有值的，我们需要去判断此时的元素、栈顶元素、栈顶之前的元素能否形成一个凹槽
# 情况一：此时的元素小于栈顶元素，凹槽的右侧不存在，无法形成凹槽
elif height[i] < height[stack[-1]]:
# 把当前索引加入到栈中
stack.append(i)
# 情况二：此时的元素等于栈顶元素，也是无法形成凹槽
elif height[i] == height[stack[-1]]:
# 把当前索引加入到栈中
stack.append(i)
# 情况三：此时的的元素大于栈顶元素，有可能形成凹槽
# 注意是有可能形成，因为比如栈中的元素是 2 、2 ，此时的元素是 3，那么是无法形成凹槽的
else :
# 由于栈中有可能存在多个元素，移除栈顶元素之后，剩下的元素和此时的元素也有可能形成凹槽
# 因此，我们需要不断的比较此时的元素和栈顶元素
# 此时的元素依旧大于栈顶元素时，我们去计算此时的凹槽面积
# 借助 while 循环来实现这个操作
while stack and height[i] > height[stack[-1]]:
# 1、获取栈顶的下标，bottom 为凹槽的底部位置
bottom = stack[-1]
# 将栈顶元素推出，去判断栈顶之前的元素是否存在，即凹槽的左侧是否存在
stack.pop()
# 2、如果栈不为空，即栈中有元素，即凹槽的左侧存在
if stack :
# 凹槽左侧的高度 height[stack[-1] 和 凹槽右侧的高度 height[i]
# 这两者的最小值减去凹槽底部的高度就是凹槽的高度
h = min(height[stack[-1]], height[i]) - height[bottom]
# 凹槽的宽度等于凹槽右侧的下标值 i 减去凹槽左侧的下标值 stack.top 再减去 1
w = i - stack[-1] - 1
# 将计算的结果累加到最终的结果上去
result += h * w
# 栈中和此时的元素可以形成栈的情况在上述 while 循环中都已经判断了
# 那么，此时栈中的元素必然不可能大于此时的元素，所以可以把此时的元素添加到栈中
stack.append(i)
# 最后返回结果即可
return result
# 四、复杂度分析
时间复杂度：O(n)，其中 n 是数组 height 的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。
空间复杂度：O(n)，其中 nn 是数组 height 的长度。空间复杂度主要取决于栈空间，栈的大小不会超过 n。